Search Results

Documents authored by Scquizzato, Michele

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2021.103
Matching on the Line Admits No o(√log n)-Competitive Algorithm

Authors: Enoch Peserico and Michele Scquizzato

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
We present a simple proof that the competitive ratio of any randomized online matching algorithm for the line exceeds √{log₂(n +1)}/15 for all n = 2ⁱ-1: i ∈ ℕ, settling a 25-year-old open question.
Cite as

Enoch Peserico and Michele Scquizzato. Matching on the Line Admits No o(√log n)-Competitive Algorithm. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 103:1-103:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{peserico_et_al:LIPIcs.ICALP.2021.103,
  author =	{Peserico, Enoch and Scquizzato, Michele},
  title =	{{Matching on the Line Admits No o(√log n)-Competitive Algorithm}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{103:1--103:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.103},
  URN =		{urn:nbn:de:0030-drops-141720},
  doi =		{10.4230/LIPIcs.ICALP.2021.103},
  annote =	{Keywords: Metric matching, online algorithms, competitive analysis}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2019.33
Equivalence Classes and Conditional Hardness in Massively Parallel Computations

Authors: Danupon Nanongkai and Michele Scquizzato

Published in: LIPIcs, Volume 153, 23rd International Conference on Principles of Distributed Systems (OPODIS 2019)

Abstract
The Massively Parallel Computation (MPC) model serves as a common abstraction of many modern large-scale data processing frameworks, and has been receiving increasingly more attention over the past few years, especially in the context of classical graph problems. So far, the only way to argue lower bounds for this model is to condition on conjectures about the hardness of some specific problems, such as graph connectivity on promise graphs that are either one cycle or two cycles, usually called the one cycle vs. two cycles problem. This is unlike the traditional arguments based on conjectures about complexity classes (e.g., P ≠ NP), which are often more robust in the sense that refuting them would lead to groundbreaking algorithms for a whole bunch of problems. In this paper we present connections between problems and classes of problems that allow the latter type of arguments. These connections concern the class of problems solvable in a sublogarithmic amount of rounds in the MPC model, denoted by MPC(o(log N)), and some standard classes concerning space complexity, namely L and NL, and suggest conjectures that are robust in the sense that refuting them would lead to many surprisingly fast new algorithms in the MPC model. We also obtain new conditional lower bounds, and prove new reductions and equivalences between problems in the MPC model.
Cite as

Danupon Nanongkai and Michele Scquizzato. Equivalence Classes and Conditional Hardness in Massively Parallel Computations. In 23rd International Conference on Principles of Distributed Systems (OPODIS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 153, pp. 33:1-33:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{nanongkai_et_al:LIPIcs.OPODIS.2019.33,
  author =	{Nanongkai, Danupon and Scquizzato, Michele},
  title =	{{Equivalence Classes and Conditional Hardness in Massively Parallel Computations}},
  booktitle =	{23rd International Conference on Principles of Distributed Systems (OPODIS 2019)},
  pages =	{33:1--33:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-133-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{153},
  editor =	{Felber, Pascal and Friedman, Roy and Gilbert, Seth and Miller, Avery},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2019.33},
  URN =		{urn:nbn:de:0030-drops-118194},
  doi =		{10.4230/LIPIcs.OPODIS.2019.33},
  annote =	{Keywords: Massively parallel computation, conditional hardness, fine-grained complexity}
}
Document
DOI: 10.4230/LIPIcs.STACS.2014.63
Efficient Computation of Optimal Energy and Fractional Weighted Flow Trade-off Schedules

Authors: Antonios Antoniadis, Neal Barcelo, Mario Consuegra, Peter Kling, Michael Nugent, Kirk Pruhs, and Michele Scquizzato

Published in: LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)

Abstract
We give a polynomial time algorithm to compute an optimal energy and fractional weighted flow trade-off schedule for a speed-scalable processor with discrete speeds. Our algorithm uses a geometric approach that is based on structural properties obtained from a primal-dual formulation of the problem.
Cite as

Antonios Antoniadis, Neal Barcelo, Mario Consuegra, Peter Kling, Michael Nugent, Kirk Pruhs, and Michele Scquizzato. Efficient Computation of Optimal Energy and Fractional Weighted Flow Trade-off Schedules. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 63-74, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{antoniadis_et_al:LIPIcs.STACS.2014.63,
  author =	{Antoniadis, Antonios and Barcelo, Neal and Consuegra, Mario and Kling, Peter and Nugent, Michael and Pruhs, Kirk and Scquizzato, Michele},
  title =	{{Efficient Computation of Optimal Energy and Fractional Weighted Flow Trade-off Schedules}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  pages =	{63--74},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-65-1},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{25},
  editor =	{Mayr, Ernst W. and Portier, Natacha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.63},
  URN =		{urn:nbn:de:0030-drops-44474},
  doi =		{10.4230/LIPIcs.STACS.2014.63},
  annote =	{Keywords: scheduling, flow time, energy efficiency, speed scaling, primal-dual}
}
Document
DOI: 10.4230/LIPIcs.STACS.2014.627
Communication Lower Bounds for Distributed-Memory Computations

Authors: Michele Scquizzato and Francesco Silvestri

Published in: LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)

Abstract
In this paper we propose a new approach to the study of the communication requirements of distributed computations, which advocates for the removal of the restrictive assumptions under which earlier results were derived. We illustrate our approach by giving tight lower bounds on the communication complexity required to solve several computational problems in a distributed-memory parallel machine, namely standard matrix multiplication, stencil computations, comparison sorting, and the Fast Fourier Transform. Our bounds rely only on a mild assumption on work distribution, and significantly strengthen previous results which require either the computation to be balanced among the processors, or specific initial distributions of the input data, or an upper bound on the size of processors' local memories.
Cite as

Michele Scquizzato and Francesco Silvestri. Communication Lower Bounds for Distributed-Memory Computations. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 627-638, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{scquizzato_et_al:LIPIcs.STACS.2014.627,
  author =	{Scquizzato, Michele and Silvestri, Francesco},
  title =	{{Communication Lower Bounds for Distributed-Memory Computations}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  pages =	{627--638},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-65-1},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{25},
  editor =	{Mayr, Ernst W. and Portier, Natacha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.627},
  URN =		{urn:nbn:de:0030-drops-44937},
  doi =		{10.4230/LIPIcs.STACS.2014.627},
  annote =	{Keywords: Communication, lower bounds, distributed memory, parallel algorithms, BSP}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact